The common and popular notion of interval arithmetic is based on the fundamental premise that intervals are sets of numbers and that arithmetic operations can be performed on these sets. Such interpretation of interval arithmetic was initially advanced by Ramon Moore in 1957, and has been recently promoted and developed by interval researchers such as Eldon Hansen, William Walster, Guy Steele and Luc Jaulin. This is the so-called “classical” interval arithmetic, and it is purely set-theoretical in nature.
A set-theoretical interval is a compact set of real numbers [a,b] such that a≦b. The classical interval arithmetic operations of addition, subtraction, multiplication and division combine two interval operands to produce an interval result such that every arithmetical combination of numbers belonging to the operands is contained in the interval result. This leads to programming formulas made famous by classical interval analysis, and which are discussed at length in the interval literature.
Translating interval programming formulas into practical computational methods that can be performed within a computer remains a topic of research in the interval community. The Institute of Electrical and Electronics Engineers Standard for Binary Floating-Point Arithmetic (i.e., IEEE standard 754), which specifies exceptionally particular semantics for binary floating-point arithmetic, enjoys pervasive and worldwide use in modern computer hardware. As a result, efforts have been focused on creating practical interval arithmetic implementations that build on the reputation and legacy of this standard.
Creating practical implementations, however, is not without its perils. The problems begin with choosing a suitable representation in a computer for the intervals. An obvious choice is to use two floating-point numbers to represent the endpoints of an interval. What is not obvious is how to handle complications which arise in conditions such as overflow, underflow and exceptional combinations of operands.
IEEE standard 754 specifies bit-patterns to represent real floating-point numbers as well as −∞, +∞, −0, +0 and the pseudo-numbers, which are called NaNs (i.e., Not-a-Number). Although the standard defines precise rules for the arithmetical combination of all permutations of bit-patterns of two floating-point values, the translation of these rules into arithmetical combinations of intervals is unclear. As is widely held, mapping the interval endpoints onto the set of IEEE floating-point representations is both desirable and challenging.
With great debate, and various levels of success, set-theoretical interval researchers have developed different representation methods for intervals. In the paper “Interval Arithmetic: from Principles to Implementation,” Hickey, et. al., Journal of the ACM, Vol. 48.5, 2001, p. 1038-1068, incorporated herein by references, the authors discuss and summarize the many different implementations and viewpoints of the interval community on this subject. In another example, Walster defines a sophisticated mapping of set-theoretical intervals to IEEE standard 754 in U.S. Pat. No. 6,658,443, which is also incorporated herein by reference.
Consensus in the interval community remains divided. As an example, the methods of both Walster and Hickey require special treatment of −0 and +0 as distinct values. However, others, like Jorge Stolfi, reject such special treatments of −0, and generally comment that while it is possible to concoct examples where such special treatment saves an instruction or two, in the vast majority of applications doing so is an annoying distraction, and a source of subtle bugs.
This observation is closely related to a problem that plagues representations of intervals in the prior art: a lack of closure or completeness. Such representations do not specify semantics for all possible bit-patterns of intervals represented by the set of IEEE floating-point numbers.
For example, in the 1997 monograph “Self-Validated Numerical Methods and Applications,” Stolfi describes a system and method for representing set-theoretical intervals within a computer, but not all possible bit-patterns are accounted for. The computational programs therein assume such bit-patterns will not appear as an operand. If the user does not take great care to submit only the valid subset of operands to the computational program, unreliable results are the inevitable and unfortunate consequence.
The same problem or shortcoming is found in the representations of Walster and Hickey. In both cases, true mathematical zero must be represented as the interval [−0,+0]. By construction, the intervals
            [                        -          0                ,                  -          0                    ]        ⁢                  [                  +        0            ,              +        0              ]    ⁢          [            +      0        ,          -      0        ]are invalid and have no semantical meaning. If great care is not taken to ensure these intervals do not appear in a computation, unreliable results occur.
Similarly, semantics do not exist, or are unclear for some intervals involving infinities. As an example, Walster's method is ambiguous on the treatment of the intervals
            [                        -          ∞                ,                  -          ∞                    ]        ⁢                  [                  +        ∞            ,              +        ∞              ]    ,whereas Stolfi unequivocally identifies such intervals as invalid.
Last but hardly least, computational simplicity is another goal that has so far been elusive. For example, the method of Walster requires significant amounts of special software instruction to create an implementation that works properly with existing hardware, with such requirement no doubt an obstacle to creating a practical implementation and/or commercial product embodying same.
In 2001, Miguel Sainz and other members of the SIGLA/X group at the University of Girona, Spain, introduced a new branch of interval mathematics known as “modal intervals.” Unlike the classical view of an interval as a compact set of real numbers, the new modal mathematics considers an interval to be a quantified set of real numbers.
As a practical consequence, a modal interval is comprised of a binary quantifier and a set-theoretical interval. In the modal interval literature, an apostrophe is used to distinguish a set-theoretical interval from a modal interval, so if Q is a quantifier and X′ is a purely set-theoretical interval, then X=(Q, X′) is a modal interval. For this reason, it is easy to see that modal intervals are a true superset of the classical set-theoretical intervals. At the same time, the quantified nature of a modal interval provides an extra dimension of symmetry not present in the classical set-theoretical framework.
This difference allows the modal intervals to solve problems out of the reach of their classical counterparts. Just as the real expression 3+x=0 has no meaning without negative numbers, it can be shown that the interval expression [1,2]+X [0,0] has no meaning without quantified (i.e., modal) intervals.
The quantified nature of a modal interval comes from predicate logic, and the value of a quantifier may be one of the fundamental constructions ∃ or ∀, that is, “existential” or “universal.” The symbols ∃ and ∀ are commonly read or interpreted as “there exists” and “for all,” respectively.
The article “Modal Intervals,” M. Sainz, et. al., Reliable Computing, Vol. 7.2, 2001, pp. 77-111, provides an in-depth introduction to the notion of modal intervals, how they differ from the classical set-theoretical intervals, and upon what mathematical framework they operate; the article is also incorporated herein by reference.
Considering that modal intervals are a new mathematical construct, a new and improved set of arithmetical operations is needed. The large body of work dealing with arithmetical operations on set-theoretical intervals is largely unhelpful due to the fact that modal intervals are mathematically more complex.
A software program for modal intervals available from the University of Girona provides a starting point or benchmark. The designers of that system avoid several implementation complexities by limiting modal intervals to those comprised only of finite and bounded endpoints. Such a representation is relatively simple to implement in a computer, but it lacks reliable overflow tracking, which can lead to pessimism and even unreliable results. This is particularly true when computations are performed in a mixed-mode environment, that is, when calculations on numbers represented by different digital scales are mixed within a lengthy computation. This occurs, for example, when some intervals in a computation are represented by 32-bit floating-point values while others have 64-bit representations.
For this reason, the previously discussed pitfalls which plague the set-theoretical operations apply to modal intervals. When considering a set of improved arithmetical operations for modal intervals, there is also the burden of supporting mathematical semantics required by modal intervals which are not present in a set-theoretical interval system, or vice-versa. Hickey defines [0,1]/[0,1]=[0,+∞] as a valid example of an expression which represents the division of two set-theoretical intervals containing zero. Such semantics do not exist in the context of modal intervals and are therefore unsuitable for, and hardly compatible with, a modal interval operation.
More recently, invalid operations of IEEE arithmetic in relation to the classical set-theoretical interval arithmetic have been addressed by Steele, Jr. in U.S. Pat. No. 7,069,288, incorporated herein by reference. In-as-much as improved results are arguably provided, the improved result values are not compatible with an unbounded modal interval framework, more particularly, Steele does not consider existential or universal quantifiers. Furthermore, and also of significance, the improved results identified by Steele depend on a rounding mode. For example, Steele defines(+∞)+(−∞)=+∞when rounding towards positive infinity and(+∞)+(−∞)=−∞when rounding in the opposite direction.
The focus of the present invention is the reliable and efficient computation of modal interval arithmetic operations. By definition, this includes modal interval addition, subtraction, multiplication and division.
In the case of the present invention, an implementation is “reliable” if it generates a mathematically correct result for any combination of operands; and the implementation is “efficient” if it requires minimal computational effort.
The prior art is filled with examples of implementations of arithmetical operations on set-theoretical intervals. Some of the examples are efficient, but none are completely reliable. In most cases, they are neither reliable nor efficient.
As a point of reference, Walster et al. describe a mask-driven division operation for set-theoretical intervals in U.S. Pat. No. 6,658,444, which is incorporated herein by reference. The basic idea of the disclosed method is to condense the complex branching logic required by the division operation into a mask, which can then be used as a switch to efficiently direct control of the software to the relevant case. Little attention is given, however, to the most crucial and important function: the actual creation of the mask. The disclosed methodology requires as much branching logic to compute the value of the mask as an implementation that is not mask-driven. As a result, the efficiency of such an implementation is questionable.
A further shortcoming of the disclosed methodology is that all cases of input are not properly considered. This can lead to unreliable computations for certain combinations of operands. As in Stolfi's “Self Validated Numerical Methods and Applications” monograph discussed earlier, Walster et al.'s method is similarly reliable only to the extent that great care is taken to submit a valid combination of operands to the division operation.
As an example, if the operands X=[+∞,+∞] and Y=[6,+∞] are submitted to Walster et al.'s TABLE 1 division operation, the operation will not properly detect the invalid IEEE arithmetic operation +∞/+∞ which occurs in the first endpoint of the result. Instead, the computational program will improperly create a mask representing case 10, and compute [+∞/+∞,+∞/6]=[NaN, +∞].
Similarly, if an invalid set-theoretical interval is submitted as an operand, Walster et al.'s TABLE 1 division operation will not detect the error in all cases. If X=[5,3] and Y=[6,9], a mask for case 10 is computed and the result [ 5/9,½] is returned. In this case, X is not a valid set-theoretical interval, nor is the result.
The methodology of Walster et al. is set primarily in the context of a software system which is under control of a compiler. As such, it is reasonable to assume that the compiler will do syntactical verification of the operands and detect such errors. But this is only true to the extent that the operands are compile-time constants in the original software source code. For example, if the operands to the interval division operation are input selectively by a user at runtime, then the compiler has no opportunity to detect that invalid operands are being submitted to the interval division operation. In such case, the inevitable result will be unreliable computations.
Similar shortcomings are likewise present in the mask-driven multiplication operation for set-theoretical intervals described in U.S. Pat. No. 6,629,120 (Walster et al.), incorporated herein by reference, as well as with the computational programs in Stolfi's previously cited monograph. The point to be made by all these examples is not to depreciate the work and contributions of prior artisans, but to illustrate the critical issue that remains: that computing reliable and efficient arithmetical operations on intervals is an exceptionally challenging problem, a problem yet to be solved.